백준 3176번

도로 네트워크

Posted by ChoiCube84 on August 19, 2023 · 22 mins read
프로그래밍 문제풀이

백준 3176번

오늘 풀어본 문제는 백준의 3176번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N$ 개의 도시와 그 도시를 연결하는 $N-1$개의 도로로 이루어진 도로 네트워크가 있다.

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 $K$개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ 이 주어진다. $(2 \leq N \leq 100,000)$

다음 $N-1$ 개 줄에는 도로를 나타내는 세 정수 $A$, $B$, $C$ 가 주어진다. $A$ 와 $B$ 사이에 길이가 $C$ 인 도로가 있다는 뜻이다. 도로의 길이는 $1,000,000$ 보다 작거나 같은 양의 정수이다.

다음 줄에는 $K$ 가 주어진다. $(1 \leq K \leq 100,000)$

다음 $K$ 개 줄에는 서로 다른 두 자연수 $D$ 와 $E$ 가 주어진다. $D$ 와 $E$ 를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

출력

총 $K$ 개 줄에 $D$ 와 $E$ 를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

풀이과정

1번째 시도

이 문제는 예전에 배웠던 LCA(최소 공통 조상) 를 이용한 문제이다. 주어지는 입력이 트리의 형태를 구성하기 때문에 두 지점 사이의 경로는 두 노드의 LCA를 지나치게 된다는 점을 이용하여 문제를 풀었다. 과정은 다음과 같다.

  1. 우선 지난번에 풀었던 LCA 2 문제2의 코드를 가져왔다.
  2. 입력을 알맞게 수정해주었다.
  3. tree 벡터를 수정하여 간선의 길이도 저장하도록 수정하였다.
  4. findLCA 함수를 이용하여 두 노드의 LCA를 출력하는 대신 findShortestAndLongestRoads 함수를 만들어 가장 짧은 도로의 길이와 긴 도로의 길이를 알아내어 출력하도록 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> tree(100001);

int depth[100001] = { 0, };
int parent[100001][18] = { 0, };
bool visited[100001] = { 0, };

void setImmediateParent(int currentNode, int currentDepth);
void setParentDP(int N);
int findLCA(int nodeA, int nodeB);

void findShortestAndLongestRoads(int nodeA, int nodeB, int& minimum, int& maximum);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, K, nodeA, nodeB, length;

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		cin >> nodeA >> nodeB >> length;

		tree[nodeA].emplace_back(make_pair(nodeB, length));
		tree[nodeB].emplace_back(make_pair(nodeA, length));
	}

	setImmediateParent(1, 0);
	setParentDP(N);

	cin >> K;

	for (int i = 0; i < K; i++) {
		int minimum = INT_MAX;
		int maximum = 0;

		cin >> nodeA >> nodeB;
		
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}

		findShortestAndLongestRoads(nodeA, nodeB, minimum, maximum);
		cout << minimum << " " << maximum << "\n";
	}

	return 0;
}

void setImmediateParent(int currentNode, int currentDepth) {
	visited[currentNode] = true;
	depth[currentNode] = currentDepth;

	for (auto i : tree[currentNode]) {
		if (visited[i.first] == false) {
			parent[i.first][0] = currentNode;
			setImmediateParent(i.first, currentDepth + 1);
		}
	}
}

void setParentDP(int N) {
	int maximumHeight = 0;

	for (int tempN = N; tempN > 1; maximumHeight++) {
		tempN >>= 1;
	}

	for (int i = 1; i <= maximumHeight; i++) {
		for (int j = 1; j <= N; j++) {
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
		}
	}
}

int findLCA(int nodeA, int nodeB) {
	if (depth[nodeA] < depth[nodeB]) {
		swap(nodeA, nodeB);
	}

	int difference = depth[nodeA] - depth[nodeB];
	int power = 0;

	while (difference > 0) {
		if (difference % 2 == 1) {
			nodeA = parent[nodeA][power];
		}
		difference = difference >> 1;
		power++;
	}

	if (nodeA == nodeB) {
		return nodeA;
	}
	else {
		for (int i = 17; i >= 0; i--) {
			if (parent[nodeA][i] != 0 && parent[nodeA][i] != parent[nodeB][i]) {
				nodeA = parent[nodeA][i];
				nodeB = parent[nodeB][i];
			}
		}

		return parent[nodeA][0];
	}
}

void findShortestAndLongestRoads(int nodeA, int nodeB, int& minimum, int& maximum) {
	bool foundNodeA = false;
	bool foundNodeB = false;

	int LCA = findLCA(nodeA, nodeB);
	stack<int> s;

	for (int currentNode = nodeA; currentNode != LCA; currentNode = parent[currentNode][0]) {
		for (auto i : tree[currentNode]) {
			if (i.first == parent[currentNode][0]) {
				minimum = min(minimum, i.second);
				maximum = max(maximum, i.second);
				break;
			}
		}
	}

	for (int currentNode = nodeB; currentNode != LCA; currentNode = parent[currentNode][0]) {
		for (auto i : tree[currentNode]) {
			if (i.first == parent[currentNode][0]) {
				minimum = min(minimum, i.second);
				maximum = max(maximum, i.second);
				break;
			}
		}
	}
}

실행 결과 ‘시간 초과’ 가 떴다.

2번째 시도

사실 채점 과정을 지켜보며 성공한 몇 가지도 시간이 오래걸려 불안하긴 했는데 결국 터지고 말았다. 문제가 되었던 부분은 역시 새로 만든 함수인 findShortestAndLongestRoads 함수가 문제였다.

이 함수는 두 노드에서 각각 LCA까지 도달하기까지 한 칸씩 부모 노드로 올라가면서 도로의 최대 길이와 최소 길이를 갱신해주는 방식으로 작동하는데, 이 과정에서 시간 초과가 발생한 것이다. 트리의 높이가 $N$ 이라고 하면 시간 복잡도가 $O(N)$ 인 것이다.

이 문제를 해결하기 위해서는 setParentDP 함수에서 어떤 노드에서 $2^k$ 차 부모 노드에 도달하기 까지 거치는 경로를 구성하는 도로들의 길이의 최댓값과 최솟값도 저장해준 뒤, findShortestAndLongestRoads 함수에서 길이를 알아내는 과정에 이 정보들을 사용해야 했다. 간단히 말하자면, 최대 길이와 최소 길이도 Sparce Table을 이용하여 저장해주어야 한다는 의미이다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> tree(100001);

int depth[100001] = { 0, };
int parent[100001][18] = { 0, };
int minimumPath[100001][18] = { 0, };
int maximumPath[100001][18] = { 0, };
bool visited[100001] = { 0, };

void setImmediateParent(int currentNode, int currentDepth);
void setParentDP(int N);
int findLCA(int nodeA, int nodeB);

void findShortestAndLongestRoads(int nodeA, int nodeB, int& minimum, int& maximum);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, K, nodeA, nodeB, length;

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		cin >> nodeA >> nodeB >> length;

		tree[nodeA].emplace_back(make_pair(nodeB, length));
		tree[nodeB].emplace_back(make_pair(nodeA, length));
	}

	setImmediateParent(1, 0);
	setParentDP(N);

	cin >> K;

	for (int i = 0; i < K; i++) {
		int minimum = INT_MAX;
		int maximum = 0;

		cin >> nodeA >> nodeB;
		
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}

		findShortestAndLongestRoads(nodeA, nodeB, minimum, maximum);
		cout << minimum << " " << maximum << "\n";
	}

	return 0;
}

void setImmediateParent(int currentNode, int currentDepth) {
	visited[currentNode] = true;
	depth[currentNode] = currentDepth;

	for (auto i : tree[currentNode]) {
		if (visited[i.first] == false) {
			parent[i.first][0] = currentNode;

			minimumPath[i.first][0] = i.second;
			maximumPath[i.first][0] = i.second;

			setImmediateParent(i.first, currentDepth + 1);
		}
	}
}

void setParentDP(int N) {
	int maximumHeight = 0;

	for (int tempN = N; tempN > 1; maximumHeight++) {
		tempN >>= 1;
	}

	for (int i = 1; i <= maximumHeight; i++) {
		for (int j = 1; j <= N; j++) {
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
			
			minimumPath[j][i] = min(minimumPath[j][i - 1], minimumPath[parent[j][i - 1]][i - 1]);
			maximumPath[j][i] = max(maximumPath[j][i - 1], maximumPath[parent[j][i - 1]][i - 1]);
		}
	}
}

int findLCA(int nodeA, int nodeB) {
	if (depth[nodeA] < depth[nodeB]) {
		swap(nodeA, nodeB);
	}

	int difference = depth[nodeA] - depth[nodeB];
	int power = 0;

	while (difference > 0) {
		if (difference % 2 == 1) {
			nodeA = parent[nodeA][power];
		}
		difference = difference >> 1;
		power++;
	}

	if (nodeA == nodeB) {
		return nodeA;
	}
	else {
		for (int i = 17; i >= 0; i--) {
			if (parent[nodeA][i] != 0 && parent[nodeA][i] != parent[nodeB][i]) {
				nodeA = parent[nodeA][i];
				nodeB = parent[nodeB][i];
			}
		}

		return parent[nodeA][0];
	}
}

void findShortestAndLongestRoads(int nodeA, int nodeB, int& minimum, int& maximum) {
	int difference, power;
	int LCA = findLCA(nodeA, nodeB);

	difference = depth[nodeA] - depth[LCA];
	power = 0;

	while (difference > 0) {
		if (difference % 2 == 1) {
			minimum = min(minimum, minimumPath[nodeA][power]);
			maximum = max(maximum, maximumPath[nodeA][power]);

			nodeA = parent[nodeA][power];
		}
		difference >>= 1;
		power++;
	}

	difference = depth[nodeB] - depth[LCA];
	power = 0;

	while (difference > 0) {
		if (difference % 2 == 1) {
			minimum = min(minimum, minimumPath[nodeB][power]);
			maximum = max(maximum, maximumPath[nodeB][power]);

			nodeB = parent[nodeB][power];
		}
		difference >>= 1;
		power++;
	}
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

오늘 이 문제를 고르게 된 것은 두 가지 이유가 있는데, 하나는 백준의 세미나 그룹에서 첫 세미나 내용에 대한 연습 가능 시간이 며칠 안남은 것이고, 다른 하나는 이미 비슷한 문제를 풀어본데다가 코드를 재활용하기 좋아보여 날먹을 기대한 것이다…

물론 그런 못된 심보를 품은 벌로 시간 초과가 발생했고, 결국 해당 내용을 제대로 다시 기억해내어 수정하는 수 밖에 없었다. 그렇다고는 해도, 꽤 빠른 시간안에 문제를 풀었고, 수정하는 것도 그리 어렵지 않았다. 그렇게 생각해보면, 어느정도는 날먹했다고 볼 수 있겠다.

앞으로는 특정 문제들을 날먹을 하겠다는 마음을 품지 않겠다. 날먹이란건 뜻하지 않게 찾아와야 날먹인 것 같다. 그리고 날먹을 하려 해도 실력이 받쳐줘야 가능한 것 같다…

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/3176
2: https://choicube84.github.io/study/2023/08/11/baekjoon_11438.html

← Previous Post Next Post →